#include <iostream>

template<typename T>
class LinkedList
{
public: 
  struct Node
  {
    T item;
    Node *next;
  };

  LinkedList() 
   : pFirst(0), pLast(0) {}
   
  void printList() {
    Node *p = pFirst;
    while (0 != p) {
      std::cout << p->item << " ";
      p = p->next;
    }
    std::cout << std::endl;
  }
  
  Node *find(T item) {
    // Complexity: O(n)
    Node *p = pFirst;
    while (0 != p) {
      if (p->item == item)
	return p;
      
      p = p->next;
    }
  }
  
  /*Node *last() {
    Node *p = pFirst;
    if (0 == p) return 0;
    do {
      p = p->next();
    } while (0 != p);
  }
  */
  
  void insert(T item) {
    // Complexity: O(1)
    Node *pNode = new Node();
    pNode->item = item;
    pNode->next = 0;
    
    if (0 == pFirst) {
      pFirst = pNode;
    }
    
    if (0 != pLast) {
      pLast->next = pNode;
    }
    
    pLast = pNode;
  }
  
  void remove(T item) {
    // Complexity: O(n)
    
    Node *p = pFirst;
    Node *pPrev = 0;
    
    while (0 != p) {
      if (p->item == item) {
	// item found
	
	// handle special cases
	if (0 != pPrev) {
	  pPrev->next = p->next;
	}
	else {
	  pFirst = p->next;
	}
	if (0 == p->next) {
	  pLast = pPrev;
	}
	
	// remove
	delete p;
	p = 0;
	return;
	
      }

      pPrev = p;
      p = p->next;
    }
  }
  
  void deleteList() {
    Node *p = pFirst;
    while (0 != p) {
      delete p;
      p = 0;
      p = p->next;
    }
  }
  
private:
  Node *pFirst;
  Node *pLast;
};

int main(int argc, char *argv[])
{
  std::cout << "a";
  LinkedList<double> ll;
  std::cout << "e" << std::endl;;
  ll.insert(1);
  std::cout << "i"  << std::endl;;
  ll.insert(9);
  ll.insert(2);
  ll.insert(8);
  std::cout << "bef"  << std::endl;;
  ll.printList();
  std::cout << "af"  << std::endl;;
  std::cout << ll.find(2)->item << std::endl;
  ll.remove(2);
  ll.printList();
  ll.remove(8);
  ll.printList();
  ll.remove(1);
  ll.printList();
  //std::cout << ll.find(2) << std::endl;
  
  
  
  return 0;
}